\section{Reducción a problema de peligrosidad de cargas}
En el punto 3 del TP 1 de la materia  se debío resolver mediante la técnica de backtracking
un problema de optimización que consistía en dado un conjunto de cargas
,conjunto de camiones y una cota sobre  al valor de peligro maximo 
que soportaba cada camión. Buscar la permutación de cargas que debía viajar
en cada camión, de manera tal que se utilicen la menor cantidad de camiones, 
dada una función de peligrosidad que asignaba un valor de peligro de a pares de cargas. 
En ese caso se trataba de minimizar la cantidad de camiones. Por lo tanto si 
2 resoluciones del problema tiene la misma cantidad de camiones,
ambas son validas como solución optima independientemente del 
peligro que suman todos los camiones juntos. \\
Si al problema anterior lo adaptamos para que en vez de obtener la menor
cantidad de camiones, nos de la distribución de cargas que hará que dado
$k$ camiones se transporte el menor valor de peligro acumulado. Entonces
resolvemos el problema k-PMP.\\

\emph{Por que este problema es similar al problema k-PMP?}\\

La resolución del problema de cargas plantea que para cada par de cargas
que tome, habrá definida una función $f(x,y) \rightarrow d$ tal que, 
ubicar ambas cargas en el mismo camión tendrá un nivel de peligro $d$.
Si pensamos en restringir las soluciones a todas aquellas de $k$ camiones
entonces esta función me dirá cual de todas las posibles distribuciones
tiene el menor peligro total(sumando el peligro de todos los camiones).\\

También hay que notar que el problema de cargas tiene un cota de peligro
por camión, esto hace que al tomar como resultado optimo en k-PMP 
el valor de peso total, en el proceso de adaptación del problema 
hay que eliminar esta cota por camión dado que esto 
cortaría posibles soluciones. Soluciones que poseen peligro 
en un camión por sobre la cota podrían llevar igualmente a
 una solución del problema k-PMP que resulte optima en el
 peso total de la solución.\\

Supongamos ahora que al problema k-PMP le adaptamos la entrada de manera tal que todos
los vértices estén conectados con todos(grafos completos). Para esto
los ejes que se agregan  al grafo tienen peso 0. 
De esta manera si dos vértices no estaban conectados, en este nuevo grafo estan conectado con un eje de peso 0, entonces si están 
 en la misma partición tendrá el mismo peso que en el grafo anterior. 

Solo modificando la entrada de k-PMP para  aumentar el dominio de la función de peso 
logramos que ambas funciones sean idénticas. \\
En el problema original k-PMP, la función $g(x,y) \rightarrow p$ 
esta definida en el dominio $(x,y) = v  \in E $ 
con $E$ los ejes del grafo. Luego de adaptar la entrada tenemos una nueva función 
$T(x,y)$ tal que si $(x,y) = v   \in E $ , $T(x,y) = g(x,y)$ , en otro caso $T(x,y) = 0$
\\
Ahora con esta función $T(x,y)$ se puede encontrar solución al problema k-PMP si 
la utilizamos como función de peligro en el problema de cagas. Quedándonos 
con la solución de menor peso para aquellas que tengan $k$ camiones 
estaremos hallando solución al problema k-PMP. \\
En resumen el proceso para llevar el problema k-PMP a el problema  de cargas se 
realizan los siguientes pasos:
\begin{itemize}
\item Se lleva el grafo de entrada a un grafo completo, donde todos los ejes 
agregados tienen peso 0
\item Se adapta el algoritmo del problema de cargas para que retorne todas las soluciones para $k$ camiones
utilizando como función de peligro $T(x,y)$
\item Se toma la solución con menor peso tal entre los $k$ camiones

\end{itemize}

\section{Reducción a problema de coloreo}
Como se explica en el planteo del problema k-PMP, las aristas intrapartición
son aquellas que conectan dos vértices dentro del mismo conjunto de la partición. 
También esta claro que si para cualquier par de vértices dentro de un mismo
conjunto de una partición no están conectados por ninguna arista, entonces el
valor del peso de la partición sera 0, dado que no existen aristas intrapartición.\\
Los problemas de coloreo tratan de encontrar relaciones de dependencia independencia 
entre pares de nodos de un grafo en base a los ejes que los conectan. \\
También es claro que la mejor solución posible para un problema k-PMP
es que la partición tenga peso 0, menos que esto no es posible.\\

\emph{Que quiere decir que la partición que resuelve k-PMP tiene peso 0?}\\

Dado un grafo podemos plantear el problema de si 
ese grafo es coloreable con exactamente $k$ colores. Esto querrá decir 
que podemos ubicar en $k$ conjuntos los vértices del grafo de manera 
que dentro de un mismo conjunto no haya ejes que los conecten entre si.
Si se encuentra la distribución que posibilita colorear con exactamente $k$
colores un grafo habremos hallado una solución optima para el problema k-PMP.
Esta solución es optima por que tendrá peso 0 dado que no hay ejes intrapartición 
para sumar.  De esta manera resolviendo un problema de coloreo 
encontramos una solución optima al problema k-PMP.  

\section{Modelado de problemas de la vida real}
\begin{itemize}
\item
Supongamos que disponemos de un conjunto de ciudades conectadas
líneas de alta tensión. Estos enlaces poseen un costo de alquiler y a su vez 
para que cada una de las ciudades este provista de suministro eléctrico
debe o poseer una central eléctrica o estar conectada a una ciudad
con suministro eléctrico. En base a  estas condiciones se debe ubicar 
sobre el conjunto de ciudades una cantidad de $k$ generadores 
de manera que se formen $k$ regiones independientes con
energía y donde el costo de la utilizaciones los enlaces debe minimizarse.\\
Las lineas que vayan desde una zona a otra no serán utilizados
y solo las que están dentro de la zona(conectan 2 ciudades dentro de la zona), 
serán alquiladas. Así se buscara minimizar el costo de los alquileres
dejando los enlaces de mayor costo fuera de las zonas.\\

Este problema puede ser modelado como un grafo en el que las lineas 
eléctricas son los ejes y los vértices son las ciudades. Así 
buscar $k$ particiones en el grafo, minimizando el peso total, resolverá
cuales son las ciudades que pertenecerán a cada zona  y dependerán del mismo generador
ubicado en cualquiera de las ciudades de la zona. \\
\item
Otro ejemplo sería tener un número $n$ de programas a ejecutar y  un número k de computadoras conectadas a una red, imaginemos que se necesita que todos los programas se estén ejecutando a la vez. Los programas estarán constantemente leyendo y modificando diferentes archivos de una computadora, pero lo que no se quiere es que dos programas distintos estén modificando el mismo archivo a la vez, o que un programa lo este leyendo cuando otro lo esté modificando (o por lo menos minimizar la probabilidad de esta situación). Además dado dos programas distintos se sabe (en base a pruebas anteriores) la probabilidad que se interfieran entre sí (obviamente que si dos programas distintos manipulan cada uno archivos distintos, la probabilidad es cero). Entonces el problema consiste encontrar la forma de distribuir los $n$ programas en las $k$ computadoras de tal manera que minimice la probabilidad de conflictos entre archivos dentro de cada una de las $k$ computadoras.\\

Se puede ver que este problema se modela con la k-Partición de Mínimo Peso donde $k$ es el número de computadoras, los nodos son los programas y las aristas la relación de conflicto entre cada par de nodos (con cierta probabilidad). El peso de las aristas sería la probabilidad. Puede pensarse que con probabilidad cero entre un par de nodos no existe una arista que los una, o que existe y esa arista tiene peso cero.
 
\end{itemize}
